package com.future;

import com.future.util.TreeNode;

import java.util.LinkedList;
import java.util.Stack;

/**
 * Description: 1161. 最大层内元素和
 * img/Solution_1161.png
 *
 * @author weiruibai.vendor
 * Date: 2023/1/11 10:04
 */
public class Solution_1161 {

    private static Solution_1161 instance = new Solution_1161();

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(7);
        root.left.left = new TreeNode(7);
        root.left.right = new TreeNode(-8);
        root.left.right.left = new TreeNode(18);


        root.right = new TreeNode(0);
        System.out.println(instance.maxLevelSum(root));
    }

    public int maxLevelSum(TreeNode root) {
        LinkedList<TreeNode> linked = new LinkedList<>();
        TreeNode nextLayerNode = root;
        Stack<TreeNode> stack = new Stack<>();
        int curLayerSum = 0;
        int curLayer = 0;
        linked.add(root);
        while (!linked.isEmpty()) {
            TreeNode curNode = linked.pollFirst();
            curLayerSum += curNode.val;
            stack.add(curNode);
            if (curNode == nextLayerNode) {
                curLayer++;
                if (curLayerSum > maxSum) {
                    maxSum = curLayerSum;
                    ans = curLayer;
                }
                nextLayerNode = null;
                while (!stack.isEmpty() && null == nextLayerNode) {
                    TreeNode pop = stack.pop();
                    nextLayerNode = pop.right != null ? pop.right : pop.left;
                }
                stack.clear();
                curLayerSum = 0;
            }
            if (curNode.left != null) {
                linked.addLast(curNode.left);
            }
            if (curNode.right != null) {
                linked.addLast(curNode.right);
            }
        }
        return ans;
    }

    int maxSum = Integer.MIN_VALUE;
    int ans = 0;
}
